# 12. O(1) 时间插入、删除和获取随机元素.py
import random
class RandomizedSet:
    def __init__(self):
        # 列表用来实际存储元素
        self.array = list()
        # 哈希表用来存储元素值在列表中的下标映射，用于快速查找。
        self.map = dict()

    def insert(self, val: int) -> bool:
        if self.map.get(val) is not None:
            return False
        else:
            self.array.append(val)
            self.map[val] = len(self.array)-1
            return True

    def remove(self, val: int) -> bool:
        if self.map.get(val) is not None:
            val_index = self.map[val]
            nail_index = len(self.array) - 1
            nail = self.array[nail_index]
            # 与尾元素换位，并删除元素
            temp = self.array[val_index]
            self.array[val_index] = self.array[nail_index]
            self.array[nail_index] = temp
            del self.array[nail_index]
            # 更新索引：
            self.map[nail] = val_index
            self.map[val] = None
            return True
        else:
            return False

    def getRandom(self) -> int:
        select = random.randint(0,len(self.array)-1)
        return self.array[select]


# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()